package q39_combinationSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_1 {


    public static void main(String[] args) {
        System.out.println(combinationSum(new int[]{2,5,2,1,2},5));
    }

    private static List<List<Integer>> res = new ArrayList<>();

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {

        // 先对数组进行排序
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        if (candidates[0] > target) {
            return res;
        }
        backtrack(path,candidates,target,0,0);
        return res;
    }

    /**
     * 典型的递归案例
     * 1 该函数没有返回值，所以在class的最开始就定义了全局变量res，之后在每一次的递归中找出符合条件的path加入到res中
     * 2 这里的path实际上可以理解为一种 枝 ，具体情况可以了解题解中的部分绘图，相当于一个n叉树
     */
    private static void backtrack(List<Integer> path, int[] candidates, int target, int sum, int begin) {
        if(sum == target) {
            // 一旦符合了条件，那么结果就会被加入到res中
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = begin;i < candidates.length;i++) {
            int rs = candidates[i] + sum;
            if(rs <= target) {
                // 这里的add代表path中加入了下一个节点
                path.add(candidates[i]);
                // 开始递归，通过画图很容易得到这一步的实际意义，就是将这个节点作为父节点，重新开始一个n叉树
                backtrack(path,candidates,target,rs,i);
                // 这一步比较特殊，也就是弹出path最后一个值，我们拿极限的情况假设一下，如果这个节点没有找到任何一个可以满足条件的path
                // 但是从前面的add得到了含有这个节点的path，那么显然这个节点是要被剔除的
                path.remove(path.size()-1);
            } else {
                break;
            }
        }
    }

}
